package org.leetcode.middle.leetcode198;


public class Solution {

    public int rob3(int[] nums) {
        int size = nums.length;

        if (size == 1) {
            return nums[0];
        }

        int[] dp = new int[size];

        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < size; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[size - 1];
    }

    public int rob2(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            //dp[i-1]表示不拿当前房间的钱，dp[i-2]+nums[i]表示拿当前房间的钱
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }

    public int rob(int[] nums) {

        if (nums.length == 0 || nums == null) {
            return 0;
        }

        if (nums.length == 1) {
            return nums[1];
        }

        //dp[0]的含义是：只有一个房间可以拿的最多的钱
        //dp[1]的含义是：有两个房间可以拿的最多的钱，即：判断第一个房间和第二个房间的谁放的钱多。
        int[] dp = new int[nums.length];

        dp[0] = nums[0];

        dp[1] = Math.max(dp[0], nums[1]);

        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
        }

        return dp[nums.length - 1];
    }
}
